NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/lang/c-part1/9146

Internet Message Format | 1996-08-05 | 3.1 KB

Path: mail2news.demon.co.uk!genesis.demon.co.uk
From: Lawrence Kirby <[e-mail]>
Newsgroups: comp.lang.c
Subject: Re: need psudeo code for binary search
Date: Wed, 06 Mar 96 21:41:51 GMT
Organization: none
Message-ID: <[e-mail]>
References: <Pine.SOL.3.91.960229154211.27358B-100000@obelix> <4h77mu$[e-mail]> <[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: genesis.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.27
X-Mail2News-Path: genesis.demon.co.uk

In article <[e-mail]>
           [e-mail] "Norman Bullen" writes:

>Donald-Anthony C. Phillips wrote:
>>
>> The binary search algorithm works as follows:
>> 1) Remember the structure must already be sorted.
>> 2) It works better as a recursive function
>It actually works better when written as a loop because it will use much
>less stack space.
>
>int BinarySearch(char *pstrTarget, char *pstrTable[], int tableSize)
>{  int comp, hi, lo, look;
>
>   hi = tableSize-1; lo = 0;
>   while (hi>=lo) {
>      look = (hi+lo)/2;
>      comp = strcmp(pstrTarget, pstrTable[look]);
>      if (comp==0) return look; /* Found it! */
>      if (comp>0)
>         lo = look+1;
>      else
>         hi = look-1;
>                  }
>   return 0; /* Didn't find it. */
>}

>(You may have to play with that piece of code a little; I think its right
>but I did not attempt any sort of testing.)

It looks apart from the last return statement however it can be marginally
simplified. When you have a range that consists of an even number of elements
you select an element that splits the rest into two subranges. Since you have
an odd number of elements left the size of the 2 subranges differ by 1. The
code above always rounds down therefore making the lower range smaller. You
can instead make the upper range smaller by changing:

       look = (hi+lo)/2;

to

       look = (hi+lo+1)/2;

This is interesting because the function as a whole can then be simplified
to:

size_t BinarySearch(char *pstrTarget, char *pstrTable[], size_t tableSize)
{  int comp;
   size_t hi, lo, look;

   hi = tableSize; lo = 0;
   while (hi>lo) {
      look = (hi+lo)/2;
      comp = strcmp(pstrTarget, pstrTable[look]);
      if (comp==0) return look; /* Found it! */
      if (comp>0)
         lo = look+1;
      else
         hi = look;
   }
   return -1; /* Didn't find it. */
}

I've changed the size parameter and the index variables to size_t for
generality since it will then work for any sized array that the
implementation can support (well, nearly, given the following).

0 is a valid success code and would indicate a match on the first element
of the array so I've changed this to -1. The value actually returned
is (size_t)-1 and since size_t is an unsigned type this corresponds to the
largest value that size_t can represent. It can be tested against (size_t)-1
in the caller function.

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------